package com.tgy.algorithm.base._二叉树;

import java.util.LinkedList;

class CBTInfo {
    boolean isCBT;
    int height;
    CBTInfo(boolean isCBT, int height) {
        this.isCBT = isCBT;
        this.height = height;
    }
}

public class _判断二叉树是否完全二叉树02 {

    public static BiTreeNode generateBiTree() {
        /**
         *          1
         *      2         3
         *   4    5
         */
        BiTreeNode header = new BiTreeNode(1);
        header.left = new BiTreeNode(2);
        header.right = new BiTreeNode(3);
        header.left.left = new BiTreeNode(4);
        header.left.right = new BiTreeNode(5);
        header.left.right.left = new BiTreeNode(6);
        header.left.right.right = new BiTreeNode(7);
//        header.right.left = new BiTreeNode(6);
//        header.right.right = new BiTreeNode(7);
        return header;
    }

    public static boolean isCompleteBiTree(BiTreeNode root) {

        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean runBorder = false;
        while (!queue.isEmpty()) {
            BiTreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            // 已经过界的，则不需要判断作用子树
            if (!runBorder && node.left != null && node.right != null) {
                continue;
            }

            if (runBorder) {
                // 过了完全二叉树的边界
                if (node.left != null || node.right != null) {
                    return false;
                }
            }else {
                // 达到完全二叉树的边界，判断边界条件
                if (node.left == null && node.right != null) {
                    return false;
                }
                runBorder = true;
            }
        }

        return true;
    }

    public static boolean isCompleteBiTree2(BiTreeNode root) {

        return doIsCompleteBiTree(root).isCBT;
    }

    public static CBTInfo doIsCompleteBiTree(BiTreeNode root) {

        if (root == null) {
            return new CBTInfo(true, 0);
        }

        CBTInfo leftInfo = doIsCompleteBiTree(root.left);
        CBTInfo rightInfo = doIsCompleteBiTree(root.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isCBT = false;

        if (leftInfo.isCBT && rightInfo.isCBT && Math.abs(leftInfo.height - rightInfo.height) <= 1) {
            isCBT = true;
        }

        return new CBTInfo(isCBT, height);
    }

    public static void main(String[] args) {
//        boolean isCBT = isCompleteBiTree(generateBiTree());
        boolean isCBT = isCompleteBiTree2(generateBiTree());
        System.out.println(isCBT);
    }
}
